[백준] 14501 - 퇴사 (파이썬)

문제

문제 링크

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

풀이

1일자부터 생각해보려 하니 도저히 답이 나오지 않았다. 각 일자별 상담마다 소요기간이 다 다르기 때문에 규칙을 찾을 수가 없기 때문이다.

그래서 퇴사일에 가까운 순으로 거꾸로 거슬러올라가며 계산해나가는 것이 편하다. 뒷날짜부터 계산해놔야 해당일자 상담의 소요시간이 끝난 후 실시할 상담에 대한 정보가 있다.

n일에 상담을 한 후 그 소요기간동안의 다른 상담들을 포기하고 n+T[n]일에 다시 상담을 하는 것이 나은지, 아니면 해당일에 상담을 하지 않는 것이 나은지 (이 경우 직전 반복에서 구해놓은 n+1일~퇴사일까지의 상담 스케줄을 선택하게 된다), 둘을 비교해서 최댓값을 저장해나가면 된다.

🤦‍♀️ 도저히 잘 이해가 안돼서 풀어 써본 계산과정…

• 퇴사 전 하루만 있는 경우, 7일자에는 상담 완료일이 퇴사일을 넘으므로 상담을 할 수 없다.
• 퇴사 전 이틀만 있는 경우, 6일자에는 상담 완료일이 퇴사일을 넘으므로 상담을 할 수 없다. 6일자 상담을 안 하고 7일자 상담을 하려고 해도 할 수 없다.

• 퇴사 전 3일(5일자~7일자)이 있는 경우,

  • 5일자에 상담을 하는 경우, 5 +T[5] = 7일자에도 상담이 가능하지만 7일자는 상담을 못하는 것이 확정이다. 그러므로 받을 수 있는 최대 금액은 5일자 상담 금액인 15이다.
  • 5일자에 상담을 하지 않고 그냥 6일자에 상담을 하려고 해도 6일자는 상담을 할 수 없다.
  • 5일자부터의 최대 금액은 15이다.

• 퇴사 전 4일(4일자~7일자)이 있는 경우,

  • 4일자에 상담을 하는 경우, 4+T[4]= 5일자에 상담이 가능하므로 받을 수 있는 금액은 20+15=35이다.
  • 4일자에 상담을 하지 않고 그냥 5일자에 상담을 한다면 받을 수 있는 금액은 (아까 구해놓은) 15이다.
  • 4일자부터의 최대 금액은 35이다.

• 퇴사 전 5(3일자~7일자)일이 있는 경우,

  • 3일자에 상담을 하는 경우, 3+T[3]=4일자에 상담이 가능하므로 받을 수 있는 금액은 10+ (아까 구해놓은) 35 = 45이다.
  • 3일자에 상담을 하지 않고 그냥 4일자에 상담을 한다면 받을 수 있는 금액은 35이다.
  • 3일자부터의 최대 금액은 45이다.

• 퇴사 전 6일(2일자~7일자)이 있는 경우

  • 2일자에 상담을 하는 경우, 2+T[2]=7일자에 상담이 가능하지만 7일자는 상담을 못하는 것이 확정이다. 그러므로 받을 수 있는 금액은 20이다.
  • 2일자에 상담을 하지 않고 그냥 3일자에 상담을 한다면 받을 수 있는 금액은 45이다.
  • 2일자부터의 최대 금액은 45이다.
• …반복…

import sys
input = sys.stdin.readline

n = int(input())
time = []
pay = []
for _ in range(n):
    t, p = map(int, input().strip().split())
    time.append(t)
    pay.append(p)

dp = [0]*(n+1)   
for i in range(n-1, -1, -1):  # 퇴사 D-1일 ~ 0일 순으로 거꾸로 탐색
    
    # i일에 하는 상담이 퇴사일을 넘기면 상담을 하지 않음
    if i+time[i] > n:  
        dp[i] = dp[i+1]
        
    # i일에 상담을 하고 i+time[i]일 후에 또다른 상담을 하는것 or i일에 상담을 안하고 그냥 i+1일부터의 스케줄을 선택하는 것 중 큰 금액을 선택 
    else:
        dp[i] = max( pay[i]+dp[i+time[i]], dp[i+1] )  
    
print(dp[0])  # 0일부터 퇴사 D-1일까지 모두 탐색한 결과인 dp[0] 반환